package com.cqs.leetcode.greedy;

class JumpGameII45 {


    //TODO 还不理解。。。。。
    public int jump(int[] nums) {
        int maxPos = 0;
        int end = 0,jp = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            //当前节点能到的最大距离
            if (nums[i] + i > maxPos) {
                maxPos = nums[i] + i;
            }
            if (end == i) {
                end = maxPos;
                ++jp;
            }
        }
        return jp;
    }


    //从后向前求。
    //假定最后一个元素的位置n， 求最小的索引m， 跳一次可以到索引n。不断重复该步骤。
    public int jump1(int[] nums) {
        //当前最后一个元素的位置
        int tail = nums.length - 1;
        int jp = 0;
        while (tail > 0) {
            for (int i = 0; i < tail; i++) {
                if (nums[i] + i >= tail) {
                    //跳一步能到最新尾部的最小索引。
                    tail = i;
                    ++jp; //跳的次数+1
                    break;
                }
            }
        }
        return jp;
    }

    //DP
    public int jump2(int[] nums) {
        //从数组首元素跳转到对应位置需要的最小步数
        int[] jp = new int[nums.length];
        //jp[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                //从j 不能直接跳到i 的位置
                if (nums[j] < i - j) {
                    continue;
                }
                if (jp[j] + 1 < min) {
                    min = jp[j] + 1;
                }
            }
            jp[i] = min;
        }
        return jp[nums.length - 1];
    }

    public static void main(String[] args) {
        int[] test = {2, 3, 1, 1, 4};
        JumpGameII45 s = new JumpGameII45();
        int val = s.jump(test);
        System.out.println(val);
    }
}